/*
 * @lc app=leetcode.cn id=105 lang=golang
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// 1. 递归
// 前序遍历：根节点, 左子树的前序遍历结果, 右子树的前序遍历结果
// 中序遍历：左子树的中序遍历结果, 根节点, 右子树的中序遍历结果
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}

	i := 0
	for ; i < len(inorder) && inorder[i] != preorder[0]; i++ {
	}

	return &TreeNode{preorder[0], buildTree(preorder[1:i+1], inorder[0:i]), buildTree(preorder[i+1:], inorder[1+i:])}
}

// @lc code=end

